/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ads.tree;

/**
 *
 * @author framet-lap
 */
public class BinarySearchTree {

    private int height;
    private int heightMessuringHelper;

    private static class Node {

        int key;
        String value;
        Node left;
        Node right;

        /**
         *
         * @param key key of the node, i.e. an id or a postal code
         * @param value value which the node contains, i.e. a persons name or a
         * city name
         */
        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    private Node root;

    /**
     * Constructs a tree with the given parameters for the root node
     *     
* @param firstKey first key used as root key
     * @param firstValue value of the root node
     */
    public BinarySearchTree(int firstKey, String firstValue) {
        this.root = new Node(firstKey, firstValue);
    }

    /**
     * Constructs a tree without an entry
     */
    public BinarySearchTree() {
    }

    /**
     * Looks for the given key and returns the associated value.
     *     
* @param key key to search for
     * @return value associated with the key, null if it does not exist
     */
    //We don't use the exist method because we dont want to loop through the tree again.
    public String find(int key) {
        Node node = find(root, key);
        if (node.key == key) {
            return node.value;
        }
        return "Not found";
    }

    private Node find(Node parent, int key) {
        if (parent.key < key && parent.right != null) {
            return find(parent.right, key);
        } else if (parent.key > key && parent.left != null) {
            return find(parent.left, key);
        } else {
            return parent;
        }
    }

    /**
     * Checks whether the given key is in the tree using binary search.
     *     
* @param key key to look for
     * @return <code>true</code> when key exists in tree, <code>false</code>
     * otherwise.
     */
    public boolean exists(int key) {
//implement
        return find(root, key).key == key;
    }

    /**
     * Inserts the a node with the given key and value at the correct place in
     * the search tree.
     *
     * @param key key of the node to add
     * @param key value of the node to add
     */
    public void insert(int key, String value) {
//implement

        insertCeption(root, root, new Node(key, value));

//        Node newNode = new Node(key, value);
//        Node parent = find(root, key);
//        if (parent.key == key) {
//            parent.value = value;
//        } else if (parent.key < key) {
//            Node right = parent.right;
//            parent.right = newNode;
//            if (right != null) {
//                newNode = right;
//            }
//        } else {
//            Node left = parent.left;
//            parent.right = newNode;
//            if (left != null) {
//                newNode = left;
//            }
//        }
    }

    public void insertCeption(Node parent, Node active, Node insert) {
        if (active != null) {
            if (active.key < insert.key) {
                insertCeption(active, active.right, insert);
            } else if (active.key > insert.key) {
                insertCeption(active, active.left, insert);
            } else {
                active.value = insert.value;
            }
        } else {
            if (parent.key < insert.key) {
                parent.right = insert;
            } else {
                parent.left = insert;
            }
        }
    }

    /**
     * Removes the node with the given key
     *
     * @param key key of the node to remove
     */
    public void delete(int key) {
//implement
// Be carefull, root has no parent. If you delete the root you can't
// update the reference of its parent. Instead update the reference of
// the root variable.

        if (root.key == key) {
            Node newRoot = findMostLeftFromRightBranche(root);
            if (root == newRoot && root.right != null) {
                newRoot = root.right;
                newRoot.left = root.left;
                root = newRoot;
            } else {
                if (newRoot.right != null) {
                    findParentBigger(newRoot, 1).left = newRoot.right;
                }
                newRoot.right = root.right;
                newRoot.left = root.left;
                root = newRoot;
            }
        } else {
            //gleich wie root aber mit parent
        }
    }

    private Node findMostLeftFromRightBranche(Node node) {
        if (node.left != null) {
            return findMostLeftFromRightBranche(node.left);
        } else {
            return node;
        }
    }

//    private Node findParentBigger(Node, int keyDifference, int smamlle)
//    private Node findParentBigger(Node node, int keyDifference, int smallerBigger){
    private Node findParentBigger(Node node, int keyDifference) {
        Node possibleParentBigger = find(root, node.key + keyDifference);
        if (possibleParentBigger.left == node) {
            return possibleParentBigger;
        } else {
            return findParentBigger(node, keyDifference + 1);
        }
    }

    /**
     * Returns the number of nodes in the tree
     *
     * @return the number of nodes in the tree
     */
    public int size() {
//implement
        return preOrderSize(root);
    }

    private int preOrderSize(Node node) {
        if (node != null) {
            return 1 + preOrderSize(node.left) + preOrderSize(node.right);
        } else {
            return 0;
        }
    }

    /**
     * Returns the height of the tree
     *
     * @return the height of the tree
     */
    public int height() {
//implement
        return preOrderHeight(root);
    }

    private int preOrderHeight(Node node) {
        if (node != null) {
            int elementsLeft = preOrderSize(node.left);
            int elementsRight = preOrderSize(node.right);
            if (elementsLeft < elementsRight) {
                return 1 + elementsRight;
            } else {
                return 1 + elementsLeft;
            }
        } else {
            return 0;
        }
    }

    private void setHeight(int height) {
        if (this.height < height) {
            this.height = height;
        }
    }

    public void doPreorder(Visitor visitor) {
        doPreorderRecursive(visitor, root);
    }

    public void doPreorderRecursive(Visitor visitor, Node node) {
        if (node != null) {
            visitor.visit(node.key, node.value);
            doPreorderRecursive(visitor, node.left);
            doPreorderRecursive(visitor, node.right);
        }
    }

    public void doInorder(Visitor visitor) {
        doInorderRecursive(visitor, root);
    }

    public void doInorderRecursive(Visitor visitor, Node node) {
        if (node != null) {
            doInorderRecursive(visitor, node.left);
            visitor.visit(node.key, node.value);
            doInorderRecursive(visitor, node.right);
        }
    }

    public void doPostorder(Visitor visitor) {
        doPostorderRecursive(visitor, root);
    }

    public void doPostorderRecursive(Visitor visitor, Node node) {
        if (node != null) {
            doInorderRecursive(visitor, node.left);
            doInorderRecursive(visitor, node.right);
            visitor.visit(node.key, node.value);
        }
    }

    private static class CrazySwazyInsertInceptionException extends RuntimeException {

        public CrazySwazyInsertInceptionException() {
        }
    }
}
